#include <stdio.h>
#include <stdlib.h>

//定义双向链表的节点
typedef struct line {
    //指向上一个节点的指针
    struct line *prior;
    //数据
    int data;
    //指向下一个节点的指针
    struct line *next;
} line;

//初始化链表
line *initLine(line *head);

//打印链表数据
void displayLine(line *head);

//插入
line *insertLine(line *head, int location, int data);

//查询
int queryLine(line *head, int wantNum);

//更新
line *updateLine(line *head, int location, int data);

//删除
line *delLine(line *head, int data);

int main() {
    //创建一个指针
    line *head = NULL;
    //初始化链表
    head = initLine(head);
    //打印链表
    displayLine(head);
    //双向链表的优点是可以方便的拿到自己的上一个节点
    printf("链表中的第4个节点的直接前驱是： %d\n", head->next->next->next->prior->data);
    printf("--------------------\n");
    //插入数据
    printf("为链表第 %d 个位置新增数据 %d \n", 3, 10);
    head = insertLine(head, 3, 10);
    displayLine(head);
    printf("--------------------\n");
    //查询
    printf("查询%d所在的位置 \n", 10);
    int location = queryLine(head, 10);
    printf("%d所在的位置是 %d \n", 10, location);
    printf("查询%d所在的位置 \n", 20);
    location = queryLine(head, 20);
    printf("%d所在的位置是 %d \n", 20, location);
    printf("查询%d所在的位置 \n", 5);
    location = queryLine(head, 5);
    printf("%d所在的位置是 %d \n", 5, location);
    displayLine(head);

    printf("--------------------\n");
    //修改
    printf("把第 %d 位的数据替换为 %d \n", 4, 22);
    head = updateLine(head, 4, 22);
    displayLine(head);
    printf("--------------------\n");
    //删除
    printf("删除值为%d的节点 \n", 22);
    head = delLine(head, 22);
    displayLine(head);

    return 0;
}

//初始化链表
line *initLine(line *head) {
    head = (line *) malloc(sizeof(line));
    head->data = 1;
    head->prior = NULL;
    head->next = NULL;

    line *tempHead = head;
    for (int i = 2; i <= 5; ++i) {
        //初始化一个新节点
        line *newNode = (line *) malloc(sizeof(line));
        newNode->data = i;
        newNode->next = NULL;
        newNode->prior = NULL;

        //把上一个节点指向新节点
        tempHead->next = newNode;
        //新节点的前置节点指向上一个节点
        newNode->prior = tempHead;
        //当前节点设置为新节点
        tempHead = tempHead->next;
    }

    return head;
}


//打印链表
void displayLine(line *head) {
    // 1 <-> 2 <-> 3 -> 0
    line *temp = head;
    while (temp) {
        //最后一个节点
        if (temp->next == NULL) {
            printf("%d \n", temp->data);
        } else {
            printf("%d <-> ", temp->data);
        }
        //暂存下一个节点
        temp = temp->next;
    }
}

//插入数据,data 是要增加的数据,location 是指定的位置
line *insertLine(line *head, int location, int data) {
    //1. 创建一个新的节点，并分配内存
    //2. 找到指定位置上的节点
    //3. 找到的节点 prior 设置为新节点
    //4. 新节点的next指向找到的节点
    //5. 找到的节点的上一个节点的next指向新节点

    line *newNode = (line *) malloc(sizeof(line));
    newNode->data = data;
    newNode->prior = NULL;
    newNode->next = NULL;

    //临时指针，指向当前节点
    line *temp = head;

    //插入到链表头
    if (location == 1) {
        newNode->next = temp;
        temp->prior = newNode;
        head = newNode;
    } else {

        line *tempNode = head;
        //找到指定位置的上一个节点 location - 1
        for (int i = 1; i < location - 1; i++) {
            tempNode = tempNode->next;
            if (tempNode == NULL) {
                printf("插入位置有误\n");
                break;
            }
        }

        if (tempNode) {
            //链表尾巴
            if (tempNode->next == NULL) {
                tempNode->next = newNode;
                newNode->prior = tempNode;
                //其他节点
            } else {
                tempNode->next->prior = newNode;
                newNode->next = tempNode->next;
                tempNode->next = newNode;
                newNode->prior = tempNode;
            }
        }


    }

    return head;
}

//查询
int queryLine(line *head, int wantNum) {
    int i = 1;
    line *t = head;
    while (t) {
        if (t->data == wantNum) {
            return i;
        }
        i++;
        t = t->next;
    }

    return -1;
}

//更新
line *updateLine(line *head, int location, int data) {
    line *tempHead = head;
    for (int i = 1; i < location; i++) {
        tempHead = tempHead->next;
        if (tempHead == NULL) {
            printf("更改数据的位置有误 \n");
            break;
        }
    }
    if (tempHead) {
        tempHead->data = data;
    }

    return head;
}

//删除
line *delLine(line *head, int data) {
    line *temp = head;
    //遍历链表
    while (temp) {
        //判断当前结点中数据域和data是否相等，若相等，摘除该结点
        if (temp->data == data) {
            temp->prior->next = temp->next;
            temp->next->prior = temp->prior;
            free(temp);
            return head;
        }
        temp = temp->next;
    }
    printf("没有找到要删除的元素\n");
    return head;
}
